#include "BST.h"
#include <stdio.h>
#include <stdlib.h>

static inline void check_MALLOC(BSTNode *root)
{
    if (!root)
    {
        fprintf(stderr, "Memory allocation failed\n");
        exit(EXIT_FAILURE);
    }
}
static inline BSTNode *newTreeNode(BSTDataType data)
{
    BSTNode *newnode = (BSTNode *)malloc(sizeof(BSTNode));
    check_MALLOC(newnode);
    newnode->data = data;
    newnode->left = NULL;
    newnode->right = NULL;
    return newnode;
}
static inline void delete_Node(BSTNode *node)
{
    free(node);
}
//初始化
BST *newBST()
{
    BST *bst = (BST *)malloc(sizeof(BST));
    bst->root = NULL;
    bst->init = BSTInit;
    bst->isEmpty = BSTIsEmpty;
    bst->add = BSTInsert;
    bst->insert = BSTInsert;
    bst->remove = BSTRemove;
    bst->search = BSTSearch;
    bst->size = BSTSize;
    bst->contains = BSTContains;
}
void BSTInit(BST *self) 
{ 
    self->root = NULL; 
    self->init = BSTInit;
    self->isEmpty = BSTIsEmpty;
    self->add = BSTInsert;
    self->insert = BSTInsert;
    self->remove = BSTRemove;   
    self->search = BSTSearch;
    self->size = BSTSize;
    self->contains = BSTContains;
}
// 判空
bool BSTIsEmpty(BST *self) { return self->root == NULL ? true : false; }

// 插入操作
int BSTInsert(BST *self, BSTDataType data)
{
    BSTNode *newNode = newTreeNode(data);
    if (!self->root)
        self->root = newNode;
    BSTNode *parent = NULL;
    BSTNode *cur = self->root;
    while (cur != NULL)
    {
        if (cur->data < data)
        {
            parent = cur;
            cur = cur->right;
        }
        else if (cur->data == data)
        {
            return 1; // 失败，已经存在
        }
        else
        {
            parent = cur;
            cur = cur->left;
        }
    }
    if (parent->data < data)
        parent->right = newNode;
    else
        parent->left = newNode;

    return 0; // 成功执行
}
// 删除操作
int BSTRemove(BST *bst, BSTDataType data);
// 返回树的大小
int BSTSize(BST *root, int *result);
/**
 * @param result 通过传递二级指针来返回找到的节点
 * @return 0:表示函数成功执行,否则程序执行异常
 */
int BSTSearch(BST *self, BSTDataType data, BSTNode **result)
{
    if (!self->root)
        return 0;
    BSTNode *cur = self->root;
    BSTNode *parent = NULL;
    while (cur != NULL)
    {
        if (cur->data < data)
        {
            parent = cur;
            cur = cur->right;
        }
        else if (cur->data == data)
        {
            if (result)
                *result = cur;
            return 0; // 成功,找到了
        }
        else
        {
            parent = cur;
            cur = cur->left;
        }
    }
    if (result)
        *result = NULL;
    return 0; // 失败，没找到
}
int BSTContains(BST *self, BSTDataType data, bool *result)
{
    if (!self->root)
        return 0;
    BSTNode *cur = self->root;
    BSTNode *parent = NULL;
    while (cur != NULL)
    {
        if (cur->data < data)
        {
            parent = cur;
            cur = cur->right;
        }
        else if (cur->data == data)
        {
            if (result)
                *result = true;
            return 0; // 成功,找到了
        }
        else
        {
            parent = cur;
            cur = cur->left;
        }
    }
    if (result)
        *result = false;
    return 0; // 失败，没找到
}

static inline int Size(BSTNode *root)
{
    if (NULL == root)
        return 0;
    else
    {
        return Size(root->left) + Size(root->right) + 1;
    }
}
int BSTSize(BST *self, int *result)
{
    *result = Size(self->root);
    return 0; // 成功执行
}

static inline void removeNode(BST *self, BSTNode *parent, BSTNode *cur)
{
    // 单叶子节点or单分支节点
    if (cur->left == NULL)
    {
        if (self->root == cur)
        {
            self->root = cur->right;
            delete_Node(cur);
        }
        else // self->root!=cur
        {
            parent->right = cur->right;
            delete_Node(cur);
        }
    }
    else if (cur->right == NULL)
    {
        if (self->root == cur)
        {
            self->root = cur->left;
            delete_Node(cur);
        }
        else // self->root!=cur
        {
            parent->left = cur->left;
            delete_Node(cur);
        }
    }
    else
    {
        BSTNode *prev = cur;
        BSTNode *pcur = cur->left;
        while (pcur->right != NULL)
        {
            prev = pcur;
            pcur = pcur->right;
        }
        cur->data = pcur->data;
        if (prev->left == pcur)
            prev->left = pcur->left;
        else
            prev->right = pcur->left;
        delete_Node(pcur);
    }
}
int BSTRemove(BST *self, BSTDataType data)
{
    if (!self->root)
        return 0;
    BSTNode *cur = self->root;
    BSTNode *parent = NULL;
    while (cur != NULL)
    {
        if (cur->data < data)
        {
            parent = cur;
            cur = cur->right;
        }
        else if (cur->data == data)
        {
            removeNode(self, parent, cur);
            return 0; // 执行成功
        }
        else
        {
            parent = cur;
            cur = cur->right;
        }
    }
}